package q926_minFlipsMonoIncr;

public class Solution_1 {
    /*
    考虑使用动态规划的方式来解决该问题，首先如果一个字符串 由0 - i-1 都是单调递增
    并且i-1 - i也能够满足规律 ，那么0 - i也是满足单调递增的，由于字符串 s 的每个位置的字符可以是 0 或 1，
    因此对于每个位置需要分别计算该位置的字符是 0 和该位置的字符是 1 的情况下的最小翻转次数
    也就是 如果我们将最后这个位置必须置为0时，此时要翻转多少次；或者最后一个必须置为1时，则要翻转多少次
    我们用dp[i][0]和dp[i][1]分别代表当字符串到达i时 如果i位置是0或者1所需要的最小翻转次数
    初始化时，也就是当i为0时，此时一定满足单调递增的条件

    当 1≤i<n 时，考虑下标 i 处的字符。如果下标 i 处的字符是 0，则只有当下标i−1 处的字符是 0 时才符合单调递增；
    如果下标 i 处的字符是 1，则下标 i−1 处的字符是 0 或 1 都符合单调递增，
    此时为了将翻转次数最小化，应分别考虑下标 i−1 处的字符是 0 和 1 的情况下需要的翻转次数，取两者的最小值。
    最后考虑当前i位置的字符是什么 是否需要翻转

    最后考虑两种情况哪种需要的次数最小
     */
    public int minFlipsMonoIncr(String s) {
        int n = s.length();
        int[][] dp = new int[n][2]; // 长度为i，最后一位为j的翻转次数
        char[] c = s.toCharArray();
        dp[0][0] = c[0] == '0' ? 0 : 1;
        dp[0][1] = c[0] == '1' ? 0 : 1;
        for (int i = 1; i < n; i++) {
            dp[i][0] = dp[i - 1][0] + (c[i] == '0' ? 0 : 1); // 当前最后一位为0则上一位肯定只能为0
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][1]) + (c[i] == '1' ? 0 : 1);
        }
        return Math.min(dp[n - 1][0], dp[n - 1][1]);
    }
}
